package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 109. 有序链表转换二叉搜索树
 * @date 2025/5/21 11:37
 */
public class E109 {

    /**
     * 方法一：操作链表
     *
     * @param head 链表头结点
     * @return 二叉搜索树
     */
    public TreeNode sortedListToBST1(ListNode head) {
        return buildTree(head, null);
    }

    private TreeNode buildTree(ListNode head, ListNode tail) {
        if (head == tail) return null;
        ListNode slow = head, fast = head;
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = buildTree(head, slow);
        root.right = buildTree(slow.next, tail);
        return root;
    }

    /**
     * 方法二：转成集合
     *
     * @param head 链表头结点
     * @return 二叉搜索树
     */
    public TreeNode sortedListToBST2(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        while (head != null) {
            nums.add(head.val);
            head = head.next;
        }
        return buildTree(nums, 0, nums.size() - 1);
    }

    private TreeNode buildTree(List<Integer> nums, int left, int right) {
        if (left > right) return null;
        int mid = (left + right) >>> 1;
        TreeNode root = new TreeNode(nums.get(mid));
        root.left = buildTree(nums, left, mid - 1);
        root.right = buildTree(nums, mid + 1, right);
        return root;
    }
}
